package 剑指offer;

public class p56_I数组中数字出现的次数 {
    public int[] singleNumbers(int[] nums) {
        // 本题的关键，有两个只出现了一次的数字，
        // 要求：时间复杂度是O(n)，空间复杂度是O(1)，所以不能用哈希表统计法
        int x=0;
        int y=0;
        int n=0;//得到 x异或y的结果
        int m=1;//得到 x和y 第一个不相同的位数

        for (int num:nums) {
            n = n ^ num;
        }
        //n= x^y
        while ((m&n)==0) {
            m=m<<1;
        }

        for (int num:nums) {
            if ((num&m) ==0) {
                x=x^num;
            }else {
                y=y^num;
            }
        }

        return new int[] {x,y};
    }
}
